package jjn.daily;

import commons.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author Jjn
 * @since 2023/9/4 23:30
 */
public class LeetCode449 {
    public class Codec {
        
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            dfs(root, result);
            StringBuilder stringBuilder = new StringBuilder();
            for (Integer num : result) {
                stringBuilder.append(num);
                stringBuilder.append(",");
            }
            if (!stringBuilder.isEmpty()) {
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
            return stringBuilder.toString();
        }
        
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] parts = data.split(",");
            if (parts.length == 0) {
                return null;
            }
            Deque<Integer> input = new ArrayDeque<>();
            for (String part : parts) {
                input.add(Integer.parseInt(part.trim()));
            }
            return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, input);
        }
        
        private TreeNode construct(int lower, int upper, Deque<Integer> deque) {
            if (deque.isEmpty() || deque.peek() < lower || deque.peek() > upper) {
                return null;
            }
            int val = deque.pop();
            TreeNode root = new TreeNode(val);
            root.right = construct(val, upper, deque);
            root.left = construct(lower, val, deque);
            return root;
        }
        
        private void dfs(TreeNode root, List<Integer> result) {
            if (root == null) {
                return;
            }
            dfs(root.left, result);
            dfs(root.right, result);
            result.add(root.val);
        }
        
    }
}
